package pers.qianyu.month_202101.date_20210120;

import org.junit.*;
import pers.qianyu.util.*;
import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 94. 二叉树的中序遍历
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 *
 * @author mizzle rain
 * @date 2021-01-20 11:43
 */
public class InorderTraversal {
/* 递归方法过于简单，就不说了
    private List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return res;
        recur(root);
        return res;
    }

    private void recur(TreeNode root) {
        if (root != null) {
            recur(root.left);
            res.add(root.val);
            recur(root.right);
        }
    }
*/

    // 迭代遍历二叉树
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        Deque<TreeNode> st = new LinkedList<>();
        TreeNode p = root;
        while (p != null || !st.isEmpty()) {
            while (p != null) {
                st.push(p);
                p = p.left;
            }
            TreeNode cur = st.poll();
            res.add(cur.val);
            p = cur.right;
        }
        return res;
    }

    @Test
    public void test1() {
        TreeNode root = BinTreeUtil.generateBinTree(new Integer[]{1, null, 2, 3});
        List<Integer> list = new InorderTraversal().inorderTraversal(root);
        System.out.println(list);
    }
}
